package com.company.ljh.medium;
/**
 * 130.地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.Arrays;
import java.util.Collections;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/6/22 16:19
 * @version:1.0
 */
public class 机器人的运动范围 {

    int max = 0;
    public int movingCount(int m, int n, int k) {
        boolean[][] vis = new boolean[m][n];

        find(m,n,0,0,k,vis,0);
        int maxValue = max;
        max = 0;
        return maxValue;
    }
    private void find(int m,int n,int i,int j,int k,boolean[][]vis,int index){
        if(vis[i][j]){
            return ;
        } else if (isCheck(i,j,k)){
            index++;
            vis[i][j] = true;
            max++;
            if(i > 0){
                find(m,n,i-1,j,k,vis,index);
            }
            if(i < m-1){
                find(m,n,i+1,j,k,vis,index);
            }
            if(j > 0 ){
                find(m,n,i,j-1,k,vis,index);
            }
            if(j < n-1 ){
                find(m,n,i,j+1,k,vis,index);
            }
        }
    }
    private boolean isCheck(int i,int j,int k){
        int sum = 0;
        while(i != 0){
            sum += i % 10;
            i = i /10;
        }
        while(j != 0){
            sum += j % 10;
            j = j /10;
        }
        if(sum > k){
            return false;
        }else{
            return true;
        }
    }
}
